package com.lwl.Algorithmic_data_structure.Morris遍历;

public class MorrisTraversal {
    public static class Node {
        public int value;
        Node left;
        Node right;

        public Node(int data) {
            this.value = data;
        }
    }
    public static void morris1(Node head) {
        if(head == null){
            return ;
        }
        Node cur = head;
        //左子树的最右节点
        Node mostRight = null;
        while (cur != null){
            mostRight = cur.left;
            if(mostRight != null){
                //找左子树的最右节点过程
                while (mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                //找到mostRight而且它的右节点为空，就将其的右节点指向当前节点（利用空闲的指针）
                //可以看成是 第一次 遍历到这个节点 的 分支
                if(mostRight.right == null){
                    System.out.print(cur.value + " ");
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{//通过左子树最右节点的指针指向cur 遍历到这个节点（ 第二次 ） 的分支
                    mostRight.right = null;
                }
            }else{
                //可以看成是第一次遍历到这个节点 的 分支 （在左子树为空的情况下）
                System.out.print(cur.value + " ");
            }
            //走到这一步说明要么没有左子树，要么mostRight之前已经被修改现在被重新设置为null了
            cur = cur.right;
        }
    }

}
